The invention relates to a method for constructing a tree for a context tree algorithm for coding symbols, which method comprises the steps of:
-x- in dependence of a value of a symbol to be coded, adapting a value of either a first parameter or a second parameter, which values correspond to a node of said tree, PA1 -y- in dependence of a value of a previous symbol, in case the node is preceded by a previous node, continuing with step -x- for the previous node, and PA1 -z- in dependence of a value of a previous symbol, in case the node is not preceded by a previous node, creating another previous node and continuing with step -x- for said other previous node. PA1 -w- a fifth parameter d being adapted for each further node and being compared with a threshold value D after each adaptation. PA1 adaptation means for, in dependence of a value of a symbol to be coded, adapting a value of either a first parameter or a second parameter, which values are stored at at least two of said first locations, PA1 comparison means for, through dependence of a value of a previous symbol, comparing a value of a third parameter, which value is stored at at least one of the first locations, with a prefixed value, whereby, in case of a first comparison result, a value of either a first parameter or a second parameter is adapted, which values are stored at at least two of the second locations, through dependence of a value of a symbol to be coded, by using the adaptation means, and PA1 allocation means for, in case of a second comparison result, in dependence of a value of a previous symbol, allocating a value to a fourth parameter, which value is stored at at least one of the third locations, whereby, a value of either a first parameter or a second parameter is adapted, which values are stored at at least two of the third locations, through dependence of a value of a symbol to be coded, by using the adaptation means. PA1 check means for checking at least one value of at least of the first and second parameters for, in case of a first check result, activating said allocation means and for, in case of a second check result, deactivating the allocation means. PA1 further adaptation means for adapting a fifth parameter d after each adaptation of the value of either the first parameter or said second parameter, and PA1 further comparison means for comparing said fifth parameter d with a threshold value D after each further adaptation. PA1 IEEE Transactions on INFORMATION THEORY, May 1995, Volume 41, Number 3, in particular "The Context-Tree Weighting Method: Basic Properties", by F. M. J. Willems, Y. M. Shtarkov and T. J. Tjalkens, pages 653-664 PA1 EP 96202007.9 (priority/filing date Jul. 15, 1996) PA1 U.S. Pat. No. 5,534,861 PA1 EP 0 480 115 PA1 U.S. Pat. No. 5,023,611 PA1 U.S. Pat. No. 5,025,258 PA1 U.S. Pat. No. 4,286,256 PA1 U.S. Pat. No. 4,494,108 PA1 U.S. Pat. No. 5,357,250
Such a method is known from IEEE Transactions on INFORMATION THEORY, May 1995, Volume 41, Number 3, in particular "The Context-Tree Weighting Method: Basic Properties", by F. M. J. Willems, Y. M. Shtarkov and T. J. Tjalkens, pages 653-664, which article discloses a sequential universal data compression procedure for binary tree sources. By using a context tree, this procedure weights in an efficient recursive way the coding distributions corresponding to all bounded memory tree sources, and achieves a desirable coding distribution for tree sources with an unknown model and unknown parameters.
Such a method is disadvantageous because it needs a giant memory capacity.